package gcj2008.round1a;

import java.math.BigDecimal;

import org.korifey.ffalg.NumberTheory;

import common.AbstractRunner;
import common.AbstractRunner.SIZE;

public class C extends AbstractRunner {
	
	int kk = 0;
	
	@Override
	public void handleCase(int caseNumber) throws Exception {
		int n = scanner.nextInt();
		String stringres;
		if (kk++ % 2 == 0) {
			//BigDecimal d = new BigDecimal(3).add(new BigDecimal(5).s)
			double d = 3 + Math.sqrt(5);
			double res = 1;
			for (int i=0; i<n; i++) {
				res *= d;
			}
			
			stringres = String.format("%1.2f", res).split("\\.")[0];					
			
		} else {
			long mod = 1000;
			long a = 3;
			long bsqr = 5;
			
			long elt = NumberTheory.powMod(a, n, 1000);
			long res = elt;
			for (int k=1; n>=2 ; n-=2, k+=2) {
				long divisor = ((n*(n-1)) % mod) * bsqr * elt;
				long dividee = ((k*(k+1)) % mod) * a * a;
				elt = NumberTheory.divMod(divisor, dividee, mod);
				res = (res + elt)%mod;
			}
			res = res*2 % mod;
			
			stringres = Long.toString(res);			
		}
		while (stringres.length() < 3) stringres = "0"+stringres;
		out.write(stringres.substring(stringres.length()-3, stringres.length()));
		out.write("\r\n");
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) throws Exception {
		new C().init(SIZE.test).execute();
	}

}
